// https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/submissions/497919132/

// 先序遍历是根，左，右
// 我们可以将根节点的右节点先放入栈中，因为栈是先进后出，然后再将其左节点放入栈中，然后取出，
// 将其追加到右子节点上，将左子节点设置为null，最终的结果就是一个链表，这样没有建立新的链表，可以节约更少的空间

import TreeNode from "./TreeNode";


function flatten(root: TreeNode | null): void {
    // 边界的判断
    if(!root) return;
    // 栈结构
    const stack = [root];
    // 定义前一个节点
    let previous: TreeNode | null = null;

    while(stack.length){
        // 取出当前元素,这里的循环条件时当栈有长度的时候，所以下面可以添加断言，current一定存在
        const current = stack.pop()!;

        if(previous){
            previous.left = null;
            previous.right = current;
        }
        // 将当前元素的右子节点和左子节点依次加入栈中
        // 这里先放右节点，因为栈是先进后出
        const right = current.right;
        const left = current.left;
        if(right){
            stack.push(right)
        }
        if(left){
            stack.push(left)
        }

        // 存储当前节点，方便一会设置其左右子节点
        previous = current;
    }
    
};